package sort;

import org.junit.Test;

public class InsertSort {
	@Test
	public void fun() {
		int[] list = {0, 1, 2, 3, 1, 4, 2};
		insertSort_2(list);
		for(int i : list) {
			System.out.print(i + "\t");
		}
	}
	public void insertSort(int[] list) {
		int sign, temp; // sign记录空值下标，temp记录取出值
		for(int i = 1; i < list.length; i ++) {
			temp = list[i];
			sign = i;
			//如果取出值小于前一个值，则把前一个值往后移，覆盖当前值
			while(sign > 0 && list[sign - 1] > temp) {
				list[sign] = list[sign - 1];
				sign --;
			}
			list[sign] = temp;
		}
	}
	//优化插入：将数组第一个元素用来保存数据，达到减少比较次数
	public void insertSort_2(int[] list) {
		int sign, temp; // sign记录空值下标，temp记录取出值
		for(int i = 2; i < list.length; i ++) {
			temp = list[i];
			list[0] = temp;
			sign = i - 1;
			//如果取出值小于前一个值，则把前一个值往后移，覆盖当前值
			while(list[sign] > temp) {
				list[sign + 1] = list[sign];
				sign --;
			}
			list[sign + 1] = temp;
		}
	}
}
